package lu.uni.adtool.adtconverter;

import java.awt.Point;

import java.util.Collections;
import java.util.Vector;

import lu.uni.adtool.adtree.ADTNode;

/**
 * Sequence of edit commands that we can apply to tree.
 * 
 * @author Piot Kordy
 */
public class EditPath
{
  private int totalCost;
  private Vector<EditAction> actions;
  private Vector<Point> matchings;
  //private Vector<Boolean> freeMatch;
  private int removeCost;

  /**
   * Constructs an edit path with non-default costs and initial value.
   * 
   * @param removeCost cost of removing or adding a node
   * changed and possibly label
   */
  EditPath(final int removeCost, final int cost)
  {
    this.removeCost = removeCost;
    this.totalCost = cost;
    actions = new Vector<EditAction>();
    matchings = new Vector<Point>();
    //freeMatch = new Vector<Boolean>();
  }

  /**
   * Constructs a new instance.
   */
  public EditPath()
  {
  }

  /**
   * Gets the totalCost for this instance.
   *
   * @return The totalCost.
   */
  public int getCost()
  {
    return this.totalCost;
  }

  /**
   * Gets the actions for this instance.
   *
   * @return The actions.
   */
  public Vector<EditAction> getActions()
  {
    return this.actions;
  }

  /**
   * Gets the matchings for this instance.
   *
   * @return The matchings.
   */
  public Vector<Point> getMatchings()
  {
    return this.matchings;
  }


  /**
   * Gets the freeMatch for this instance.
   *
   * @return The freeMatch.
   */
  //public Vector<Boolean> getFreeMatch()
  //{
    //return this.freeMatch;
  //}

  /**
   * Create copy of the path.
   * 
   * @return a copy of the path.
   */
  public EditPath copy()
  {
    final EditPath result = new EditPath(removeCost,0);
    result.add(this);
    return result;
  }

  /**
   * Add action of removing a node from left or right tree to the end of path.
   * 
   * @param leftIndex index of the node to be removed in the left tree
   * @param rightIndex index of the node to be removed in the right tree
   * @param fromLeft true if we remove from left tree.
   * @param leftStrat true if we got here using spfL
   */
  public void rmNode(final int leftIndex,final int rightIndex,boolean fromLeft,boolean leftStrat)
  {
    if (fromLeft){
      insRightNode(leftIndex,rightIndex,leftStrat);
    }
    else{
      rmRightNode(leftIndex,rightIndex,leftStrat);
    }
  }

  /**
   * Removes node from the right tree.
   * 
   * @param leftIndex
   * @param rightIndex index of node to be removed
   * @param leftStrat
   */
  public void rmRightNode(final int leftIndex,final int rightIndex, boolean leftStrat)
  {
    EditAction.ActionType action;
    action = EditAction.ActionType.RM_NODE_RT;
    totalCost +=  removeCost;
    actions.add(new EditAction(action, leftIndex,rightIndex,leftStrat));
  }
  /**
   * Inserting into riht tree (dual to deleting from left tree)
   * 
   * @param leftIndex
   * @param rightIndex
   * @param leftStrat
   */
  public void insRightNode(final int leftIndex, final int rightIndex, boolean leftStrat)
  {
    EditAction.ActionType action;
    action = EditAction.ActionType.INS_NODE_RT;
    totalCost +=  removeCost;
    actions.add(new EditAction(action, leftIndex, rightIndex, leftStrat));
  }
  /**
   * Add another path to current path.
   * 
   * @param path path to be added.
   */
  public void add(final EditPath path)
  {
    totalCost += path.getCost();
    matchings.addAll(path.getMatchings());
    //freeMatch.addAll(0,path.getFreeMatch());
    actions.addAll(path.getActions());
  }
  /**
   * Add another path to current path.
   * 
   * @param path path to be added.
   */
  public void addRev(final EditPath path)
  {
    totalCost += path.getCost();
    //freeMatch.addAll(0,path.getFreeMatch());
    matchings.addAll(0,path.getMatchings());
    actions.addAll(0,path.getActions());
  }
  /**
   * Add matching operation.
   * 
   * @param indexLeft postorder index of left node.
   * @param indexRight postorder index of right node.
   */
  public void addMatch(final int indexLeft, final int indexRight,int matchCost)
  {
    totalCost += matchCost;
    //freeMatch.add(new Boolean(matchCost==0));
    matchings.add(new Point(indexLeft,indexRight));
  }

  /**
   * {@inheritDoc}
   * @see Object#toString()
   */
  public String toString()
  {
    if (getCost() == 0 && actions.size() == 0) {
      return "Empty_path";
    }
    String result = "cost=" + getCost();
    for (EditAction a : actions) {
      result += " " + a;
    }
    for (Point p : matchings) {
      result += " " + p;
    }
    return result;
  }

  /**
   * Sorts actions according to the postorder index.
   * 
   * @return sorted edit path.
   */
  public final EditPath sort()
  {
    Collections.sort(actions);
    return this;
  }
  public void transferLabels(final LblTree t1, final LblTree t2)
  {
    final Vector<LblTree> post2nodeL = getPostOrdering(t1);
    final Vector<LblTree> post2nodeR = getPostOrdering(t2);
    int i=0;
    for (Point p : matchings) {
      //if(freeMatch.elementAt(i)){
        final LblTree leftNode = post2nodeL.elementAt(p.x);
        if (leftNode.getType() != ADTNode.Type.LEAFO
            && leftNode.getType() != ADTNode.Type.LEAFP) {
          leftNode.setName(post2nodeR.elementAt(p.y).getName());
        }
      //}
      i++;
      //t1.setName(t2.getName());
    }

  }
  /**
   * Make right tree look like the left tree.
   * 
   * @param t1
   *          left tree.
   * @param t2
   *          right tree that is changed.
   * @return new tree.
   * 
   */
  public LblTree applyPath(final LblTree t1, final LblTree t2)
  {
    if (t1 == null || t2 == null) {
      return null;
    }
    LblTree leftFR = addFakeRoot(t1);
    LblTree rightFR = addFakeRoot(t2);
    System.out.println("t1:"+t1.toString(3));
    System.out.println("t2:"+t2.toString(3));
    System.out.println(this);
    final Vector<LblTree> post2nodeL = getPostOrdering(t1);
    final Vector<LblTree> post2nodeR = getPostOrdering(t2);
    final Vector<LblTree> post2parentR = getPost2Parent(post2nodeR);
    final int[] post2revIndexR = getPost2RevIndex(post2parentR,post2nodeR);
    final int[] post2indexR = getPost2Index(post2parentR,post2nodeR);
    final int[] right2left = getRight2LeftIndex(post2nodeR.size());
    for (EditAction a : actions) {
      final LblTree nodeLeft = post2nodeL.elementAt(a.getLeftIndex());
      final LblTree nodeRight = post2nodeR.elementAt(a.getRightIndex());
      final LblTree parentRight = post2parentR.elementAt(a.getRightIndex());
      switch (a.getType()) {
        case INS_NODE_RT:
          final int noChildren = nodeLeft.getChildren().size();
          int indexR;
          if(right2left[a.getRightIndex()]<a.getLeftIndex()){
            //we add on the right side then
            System.out.println("  APi adding on right");
            indexR = parentRight.getChildren().size()
              - post2revIndexR[a.getRightIndex()]+1;
          }
          else{
            System.out.println("  APi adding on left");
            indexR = post2indexR[a.getRightIndex()];
            post2indexR[a.getRightIndex()] = post2indexR[a.getRightIndex()] + 1
                - noChildren;
            //add on the left side
          }
          indexR = indexR - noChildren;
          System.out.println("  APi indexR:" + indexR + " noChildren:"
              + noChildren + " pL:" + a.getLeftIndex() + " pR:"
              + a.getRightIndex());
          String name = nodeLeft.getName();
          if(name.equals("")){
            name = nodeLeft.getType().toString().toLowerCase();
          }
          parentRight.addChildAt(nodeLeft.getType(),name,indexR, noChildren);
          break;
        case RM_NODE_RT:
          if (parentRight == null) {
            System.err.println("  APr RM_NODE_RT:Error - no parent for node "
                + nodeRight.getName());
            return null;
          }
          //System.out.println("  APr RM_NODE_RT:removing node:"+nodeRight+" from:"+parentRight);
          parentRight.removeChild(nodeRight);
          //System.out.println("  APr RM_NODE_RT:parent after removing:"+parentRight+" id:"+parentRight.getId());
          break;
        default:
      }
    }
    for (Point p : matchings) {
      matchNodes(post2nodeL.elementAt(p.x), post2nodeR.elementAt(p.y));
    }
    //System.out.println("Final tree\n"+t2);
    rmFakeRoot(leftFR);
    return rmFakeRoot(rightFR);
  }
  /**
   * Calculate postordering of the nodes.
   * 
   * @param t1
   * @return vector with nodes in postorder.
   */
  private Vector<LblTree> getPostOrdering(LblTree t1)
  {
    Vector<LblTree> v = new Vector<LblTree>();
    getPostOrdering(t1, v,false);
    return v;
  }
  private Vector<LblTree> getPost2Parent(Vector<LblTree> v)
  {
    Vector<LblTree> result = new Vector<LblTree>();
    for(int i=0;i<v.size();i++){
      final LblTree node = v.elementAt(i);
      result.add((LblTree)node.jjtGetParent());
    }
    return result;
  }
  private int[] getPost2RevIndex(Vector<LblTree> parents,Vector<LblTree> children)
  {
    int[] result = new int[parents.size()];
    for(int i=0;i<parents.size();i++){
      final LblTree parent = parents.elementAt(i);
      final LblTree child = children.elementAt(i);
      result[i]=parent.getChildren().size()-parent.getChildren().indexOf(child);
    }
    return result;
  }
  private int[] getPost2Index(Vector<LblTree> parents,Vector<LblTree> children)
  {
    int[] result = new int[parents.size()];
    for(int i=0;i<parents.size();i++){
      final LblTree parent = parents.elementAt(i);
      final LblTree child = children.elementAt(i);
      result[i] = parent.getChildren().indexOf(child);
    }
    return result;
  }
  private Vector<LblTree> getPostOrdering(LblTree t, Vector<LblTree> v, boolean parent)
  {
    //for (int childrenCount = t.getChildren().size(); childrenCount > 0; --childrenCount) {
      //getPostOrdering((LblTree) t.getChildren().elementAt(childrenCount - 1), v);
    //}
    for (int childrenCount = 0; childrenCount < t.getChildren().size();
        ++childrenCount) {
      getPostOrdering((LblTree) t.getChildren().elementAt(childrenCount), v, parent);
    }
    if(!parent){
      v.add(t);
    }
    else{
      v.add((LblTree)t.jjtGetParent());
    }
    return v;
  }

  private void matchNodes(final LblTree t1, final LblTree t2)
  {
    //System.out.println("match t1="+t1.getName()+" t2="+t2.getName());
    //System.out.println("match type t1="+t1.getType()+" t2="+t2.getType());
    if(t1.getType()==ADTNode.Type.LEAFP||t1.getType()==ADTNode.Type.LEAFO){
      t2.setName(t1.getName());
    }
    t2.setType(t1.getType());
  }
  private LblTree addFakeRoot(final LblTree node)
  {
    LblTree n = node;
    while (n.jjtGetParent()!=null){
      n = (LblTree)n.jjtGetParent();
    }
    final LblTree newRoot = new LblTree(-2);
    newRoot.getChildren().add(node);
    newRoot.setType(ADTNode.Type.OP);
    node.jjtSetParent(newRoot);
    newRoot.jjtSetParent(null);
    return newRoot;
    //newRoot.addChild(n);
  }
  private int[] getRight2LeftIndex(int size)
  {
    int[] result = new int[size];
    for(Point match:matchings){
      result[(int)match.getY()]=(int)match.getX();
    }
    return result;
  }
  private LblTree rmFakeRoot(final LblTree node)
  {
    LblTree n = node;
    while (n.jjtGetParent()!=null){
      n = (LblTree)n.jjtGetParent();
    }
    if (n.getId()!=-2){
      System.err.println("Failed to remove fake root");
      return n;
    }
    final LblTree result = (LblTree)n.getChildren().elementAt(0);
    n.getChildren().clear();
    result.jjtSetParent(null);
    return result;
    //n.getChildren().elementAt(n);
    //newRoot.addChild(n);
  }
}
